package cn.fxzhang.leetcode.no00;

/**
 * 81. 搜索旋转排序数组 II
 * nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1],
 * nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]
 * 给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
 * 输入：nums = [2,5,6,0,0,1,2], target = 0
 * 输出：true
 * 提示：
 * 1 <= nums.length <= 5000
 * -10^4 <= nums[i] <= 10^4
 * 题目数据保证 nums 在预先未知的某个下标上进行了旋转
 * -104 <= target <= 104
 *
 * 类型：二分查找
 * 题解：二分查找
 * 时间复杂度：O(N), N是数组中的元素数量
 * 空间复杂度：O(1)
 *
 * 提交记录(2/3)：
 * 括号放错地方，导致第一次提交答案错误
 * 执行用时: 0 ms, 击败了100.00%
 * 内存消耗: 38.3 MB, 击败了28.49%
 *
 * 【中等】通过次数78,058提交次数195,223
 * @author 张晓帆
 * @date 2021/4/7
 */
public class P0081_Search_In_Rotated_Sorted_Array_Ii {

    public boolean search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length-1);
    }

    private boolean binarySearch(int[] nums, int target, int left, int right) {
        if (left > right || nums[left] < nums[right] && (target < nums[left]|| target > nums[right])){
            return false;
        }
        int mid = (left + right) >> 1;
        if (nums[mid] == target){
            return true;
        }
        //if (nums[left] == nums[mid] && nums[mid] == nums[right]){
        //    return binarySearch(nums, target, left+1, right-1);
        //}
        return binarySearch(nums, target, left, mid-1) || binarySearch(nums, target, mid+1, right);
    }
}
